package demo.practice.stack;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class P496 {
    public static void main(String[] args) {

        P496 p496 = new P496();
        p496.nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2,5});
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        //i - index  ，i表示元素，index表示下一个比i大的数
        //[1,3,4,2,5]
        //用一个栈找到下一个比自己大的元素
        //栈里面保持逐渐增大的

        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            if (stack.isEmpty() || nums2[i] < nums2[stack.peek()]) {
                map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
                stack.add(i);
            } else {
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                    stack.pop();
                }
                map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
                stack.add(i);
            }
        }

        int res[] = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.get(nums1[i]) == -1 ? -1 : nums2[map.get(nums1[i])];
        }
        return res;
    }

}
